package com.zpself.module.算法练习.String;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 * @Description 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * 答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 */
public class 力扣_17_电话号码的字母组合 {
    //验证，代码没有错误
    public static void main(String[] args) {
        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations("23"));
    }


    //在外面定义这些变量，可以减少backTrack函数的参数，免得参数太长，头晕
    //定义res，用来装结果
    List<String> res = new ArrayList<>();
    //定义track，用来装满足条件的单个字符串
    StringBuilder track = new StringBuilder();
    //还是那句话，定义在外面，backTrack函数就不需要传这个参数了，在下面进行初始化
    String digits;
    //定义ch数组，按‘2’的时候对应ch数组的第0行，按‘3’的时候对应ch数组的第1行，下面依次类推
    char[][] ch = new char[][]{
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}};

    //题解：递归法，比较复杂
    public List<String> letterCombinations(String digits) {
        //特殊判断
        if (digits == null || digits.length() == 0) return res;
        //初始化digits
        this.digits = digits;
        //开始递归
        backTrack(0);
        //返回结果
        return res;
    }

    //唯一的一个参数的含义是：digits字符的索引，从索引0开始递归
    public void backTrack(int length) {
        //终止条件，当track字符串的长度等于digits的长度，则终止递归，把字符串加到res中
        if (track.length() == digits.length()) {
            res.add(String.valueOf(track));
            return;
        }
        //从索引0开始遍历，遍历到digits的最后一个字符
        for (int i = length; i < digits.length(); ++i) {
            //注意这里的下标计算，比如第一个字符是'2'，那么对应的字符数组是{'a','b','c'},该数组在ch数组中的索引是0，即'2' - '2'
            for (int j = 0; j < ch[digits.charAt(i) - '2'].length; ++j) {
                //做选择（回溯算法基本模板三部曲，做选择--递归--撤销选择）
                track.append(ch[digits.charAt(i) - '2'][j]);
                //递归
                backTrack(i + 1);
                //撤销选择
                track.deleteCharAt(track.length() - 1);
            }
        }
    }
}
